EN FR
EN FR


Section: Research Program

Polychronous model of computation

We consider a partially-ordered set of tags t to denote instants seen as symbolic periods in time during which a reaction takes place. The relation t1t2 says that t1 occurs before t2. Its minimum is noted 0. A totally ordered set of tags C is called a chain and denotes the sampling of a possibly continuous or dense signal over a countable series of causally related tags. Events, signals, behaviors and processes are defined as follows:

  • an evente is a pair consisting of a value v and a tag t,

  • a signals is a function from a chain of tags to a set of values,

  • a behaviorb is a function from a set of names x to signals,

  • a processp is a set of behaviors that have the same domain.

In the remainder, we write tags (s) for the tags of a signal s, vars (b) for the domain of b, b|X for the projection of a behavior b on a set of names X and b/X for its complementary.

Figure 1 depicts a behavior b over three signals named x, y and z. Two frames depict timing domains formalized by chains of tags. Signals x and y belong to the same timing domain: x is a down-sampling of y. Its events are synchronous to odd occurrences of events along y and share the same tags, e.g. t1. Even tags of y, e.g. t2, are ordered along its chain, e.g. t1<t2, but absent from x. Signal z belongs to a different timing domain. Its tags are not ordered with respect to the chain of y.

Figure 1. Behavior b over three signals x, y and z in two clock domains
IMG/figure01.png

Composition

Synchronous composition is noted p|q and defined by the union bc of all behaviors b (from p) and c (from q) which hold the same values at the same tags b|I=c|I for all signal xI= vars (b) vars (c) they share. Figure 2 depicts the synchronous composition (Figure 2 , right) of the behaviors b (Figure 2 , left) and the behavior c (Figure 2 , middle). The signal y, shared by b and c, carries the same tags and the same values in both b and c. Hence, bc defines the synchronous composition of b and c.

Figure 2. Synchronous composition of bp and cq
IMG/figure02.png

Scheduling

A scheduling structure is defined to schedule the occurrence of events along signals during an instant t. A scheduling is a pre-order relation between dates xt where t represents the time and x the location of the event. Figure 3 depicts such a relation superimposed to the signals x and y of Figure 1 . The relation yt1xt1, for instance, requires y to be calculated before x at the instant t1. Naturally, scheduling is contained in time: if t<t' then xtbxt' for any x and b and if xtbxt' then ¬(t'<t).

Figure 3. Scheduling relations between simultaneous events
IMG/figure03.png

Structure

A synchronous structure is a semi-lattice representing behaviors with the same timing structure. We interpret a signal as an elastic with ordered marks on it (tags). If the elastic is stretched, marks remain in the same relative (partial) order but have more space (time) between each other. The same holds for a set of elastics: a behavior. If elastics are equally stretched, the order between marks is unchanged.

In Figure 4 , the time scale of x and y changes but the partial timing and scheduling relations are preserved. Stretching is a partial-order relation which defines clock equivalence. Formally, a behavior c is a stretching of b of same domain, written bc, iff there exists an increasing bijection on tags f that preserves the timing and scheduling relations. If so, c is the image of b by f. Last, the behaviors b and c are said clock-equivalent, written bc, iff there exists a behavior d s.t. db and dc.

Figure 4. Relating synchronous behaviors by stretching.
IMG/figure04.png